#include "util.c"
#include <stdio.h>
#include <stdlib.h>
tree *inittree(){
    tree *t=malloc(sizeof(tree));
    t->ltree=NULL;
    t->rtree=NULL;
    return t;
}
void createtree(tree *root,int data){
    root->data=data;
    printf("输入一个数字作为其左孩子的数据，0代表没有左孩子");
    int ln;
    scanf("%d",&ln);
    if(ln!=0){
        root->ltree=inittree();
        createtree(root->ltree,ln);
    }
    printf("输入一个数字作为其右孩子的数据，0代表没有右孩子");
    int rn;
    scanf("%d",&rn);
    if(rn!=0){
        root->rtree=inittree();
        createtree(root->rtree,rn);
    }
}
void selectbeforebymethod1(tree *root){
    if(root!=NULL){
        printf("%d ",root->data);
        selectbeforebymethod1(root->ltree);
        selectbeforebymethod1(root->rtree);
    }
}
void selectbeforebymethod2(tree *root,stack *s){
    while (root!=NULL||isemptstack(*s)==0)
    {
        if(root!=NULL){
            printf("%d ",root->data);
            pushstack(s,root);
            root=root->ltree;
        }
        else{
            root=popstack(s)->rtree;
        }
        
    }
    
}
void selectafterbymethod1(tree *root){
    if(root!=NULL){
        selectafterbymethod1(root->ltree);
        selectafterbymethod1(root->rtree);
        printf("%d ",root->data);
    }
}
void selectmidbymethod1(tree *root){
    if(root!=NULL){
        selectmidbymethod1(root->ltree);
        printf("%d ",root->data);
        selectmidbymethod1(root->rtree);
    }
    
}
void selectmidbymethod2(tree *root,stack *s){
    while (root!=NULL||isemptstack(*s)==0)
    {
        if(root!=NULL){
            pushstack(s,root);
            root=root->ltree;
        }
        else{
            root=popstack(s);
            printf("%d ",root->data);
            root=root->rtree;
        }
        
    }
    
}
void selectlayer(tree root,queue *q){
    printf("%d ",root.data);
    if(root.ltree!=NULL){
        pushqueue(q,root.ltree);
    }
    if(root.rtree!=NULL){
        pushqueue(q,root.rtree);
    }
    while (isemptqueue(*q)!=1)
    {
        selectlayer(*popqueue(q),q);
    }
    
}
void main(){
    tree *t=inittree();
    createtree(t,12);
    printf("使用递归方式实现先序遍历：");
    selectbeforebymethod1(t);
    printf("\n");
    printf("使用非递归方式实现先序遍历：");
    stack *sbefore=initstack();
    selectbeforebymethod2(t,sbefore);
    printf("\n");
    printf("后序遍历：");
    selectafterbymethod1(t);
    printf("\n");
    printf("使用递归方式实现中序遍历：");
    selectmidbymethod1(t);
    printf("\n");
    printf("使用非递归方式实现中序遍历：");
    stack *smid=initstack();
    selectmidbymethod2(t,smid);
    printf("\n");
     printf("层次遍历：");
     queue *q=initqueue();
    selectlayer(*t,q);
    printf("\n");
}